package num08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MerageQuJian {
    public int[][] merge(int[][] intervals) {
       //折叠区间其实就是，按照排序之后，判断前面集合的右边届是否小于下一个的左边届也就是这个区间内最大的元素知否小于下一个集合中最小的
        //这样就保证了不相交
        // 对所有的区间按照起始顺序进行排序
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        // 定义一个pre变量  初始值为null
        int[] pre = null;
        // result  用来存放结果
        List<int[]> result = new ArrayList<>();
        // 从头开始遍历所有的区间
        for (int[] num : intervals) {
            // 如果这是第一个区间，或者当前区间和上一个区间没有重叠，那么将当前区间加入到结果中
            if (pre == null || pre[1] < num[0]) {
                result.add(pre = num);
            } else {
                // 否则两个区间发生了重叠，更新第一个区间的结束值
                pre[1] = Math.max(pre[1], num[1]);
            }
        }
        // 返回结果
        return result.toArray(new int[result.size()][]);

    }
}
